package cn.antblog.ruankao.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName NQueens
 * @Description 回溯法解决N皇后问题
 * @Author YangJingyi
 * @Date 2023/9/22 9:07
 * @Version 1.0
 */
/*
    这段代码中，solveNQueens方法接收一个整数n，表示棋盘的大小，然后调用backtrack方法开始回溯求解。backtrack方法用于逐行放置皇后，row表示当前行数。在每一行，通过循环遍历每一列，尝试放置皇后。如果当前位置合法，就将皇后放置在该位置，然后递归调用backtrack方法处理下一行。如果当前位置不合法，就尝试下一列。当row等于n时，说明已经找到一个合法解，调用addSolution方法将解添加到solutions列表中。

    isValid方法用于验证当前位置是否合法。它遍历之前已经放置的皇后，检查是否存在冲突。如果存在同一列或同一对角线上的皇后，就返回false，否则返回true。

    addSolution方法用于将一个合法解添加到solutions列表中。它将每一行的皇后位置转换为字符串表示，并添加到solution列表中，最后将solution列表添加到solutions列表中。

    使用该代码可以解决N皇后问题，并返回所有解的列表。每个解都是一个字符串列表，表示皇后在棋盘上的放置方式。其中，'Q'表示皇后，'.'表示空白位置。
 */
public class NQueens {
    private int[] queens; // 皇后在每一行的位置
    private int n; // 棋盘大小
    private List<List<String>> solutions; // 存储所有解的列表

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        queens = new int[n];
        solutions = new ArrayList<>();
        backtrack(0);
        return solutions;
    }

    private void backtrack(int row) {
        if (row == n) {
            addSolution();
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isValid(row, col)) {
                queens[row] = col;
                backtrack(row + 1);
            }
        }
    }

    private boolean isValid(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (queens[i] == col || Math.abs(queens[i] - col) == row - i) {
                return false;
            }
        }
        return true;
    }

    private void addSolution() {
        List<String> solution = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append(queens[i] == j ? 'Q' : '.');
            }
            solution.add(sb.toString());
        }
        solutions.add(solution);
    }
}
